package com.lft.stack.poland.calculator;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author Laifengting
 */
public class PolandNotation {
	public static void main(String[] args) {
		// 完成将一个中缀表达式转换成后缀表达式的功能
		// 说明：
		// 1. 1+((2+3)*4)-5  =>  1 2 3 + 4 * + 5 -
		// 2. 因为直接对 String 进行操作不方便，因此先将 1+((2+3)*4)-5 中缀表达式转换成中缀的表达式对应的List
		//  	即 1+((2+3)*4)-5 => ArrayList[1,+,(,(,2,+,3,),*,4,),-,5]
		// 3. 将得到的中缀表达式对应的 List 转换成 后缀表达式对应的 List
		//		即 ArrayList[1,+,(,(,2,+,3,),*,4,),-,5] => ArrayList[1,2,3,+,4,*,+,5,-]
		String infixExpression = "1+((2+3)*4)-5";
		// 中缀表达式转成对应的 List
		List<String> list = toInfixExpressionList(infixExpression);
		System.out.println(list);
		
		// 中缀表达式对应的 List 转成 后缀表达式转成对应的 List
		List<String> suffixExpressionList = toSuffixExpressionList(list);
		System.out.println(suffixExpressionList);
		
		int calculate = calculate(suffixExpressionList);
		System.out.println("rpnList" + suffixExpressionList);
		System.out.println("计算结果" + calculate);
		
		// // 先定义逆波兰表达式
		// // (3 + 4) × 5 - 6 = 3 4 + 5 × 6 -
		// // 说明：为了方便，逆波兰表达式的数字和符号使用空格隔开。
		// // String suffixExpression = "30 4 + 5 * 6 -";
		// String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
		//
		// // 1. 先将表达式 `3 4 + 5 × 6 -` 放到 ArrayList 中。
		// // 2. 将 ArrayList 传递给一个方法。遍历 ArrayList 配合栈完成计算。
		// List<String> rpnList = getListString(suffixExpression);
		// int calculate = calculate(rpnList);
		// System.out.println("rpnList" + rpnList);
		// System.out.println("计算结果" + calculate);
	}
	
	/**
	 * 将中缀表达式的 List 转换成 后缀表达式的 List
	 * 即 ArrayList[1,+,(,(,2,+,3,),*,4,),-,5] => ArrayList[1,2,3,+,4,*,+,5,-]
	 */
	public static List<String> toSuffixExpressionList(List<String> infixExpressionList) {
		// 1. 定义两个栈
		// 符号栈
		Stack<String> s1 = new Stack<>();
		// 因为 s2 这个栈，在整个转换过程中，没有 pop 操作，而且后面我们还需要逆序输出。
		// 因此比较麻烦，这里我们就不用 Stack<String>，直接使用 List<String> s2
		// 存储中间结果的栈 s2
		// Stack<String> s2 = new Stack<>();
		// 存储中间结果的 s2
		List<String> s2 = new ArrayList<>();
		
		// 遍历 中缀表达式对应的 List
		// 2. 从左至右扫描中缀表达式；
		for (String item : infixExpressionList) {
			// 3. 如果是一个数，就加入到 s2
			if (item.matches("\\d+")) {
				s2.add(item);
			}
			// 5.1 如果是左括号“(”，则直接压入s1
			else if ("(".equals(item)) {
				s1.push(item);
			}
			// 5.2 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
			else if (")".equals(item)) {
				while (!"(".equals(s1.peek())) {
					s2.add(s1.pop());
				}
				// 将 ( 弹出栈
				s1.pop();
			} else {
				// 4.3 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
				while (s1.size() != 0 && !"(".equals(s1.peek()) && Operation.getPriority(s1.peek()) >= Operation.getPriority(item)) {
					s2.add(s1.pop());
				}
				// 4.1 遇到运算符时，比较其与s1栈顶运算符的优先级：如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
				// 4.2 否则，若优先级比栈顶运算符的高，也将运算符压入s1；
				s1.push(item);
			}
		}
		// 将s1中剩余的运算符依次弹出并压入s2
		while (s1.size() != 0) {
			s2.add(s1.pop());
		}
		return s2;
	}
	
	/**
	 * 将中缀表达式转成对应的 List
	 * 因为直接对 String 进行操作不方便，因此先将 1+((2+3)*4)-5 中缀表达式转换成中缀的表达式对应的List
	 * 即 String "1+((2+3)*4)-5" => ArrayList[1,+,(,(,2,+,3,),*,4,),-,5]
	 */
	public static List<String> toInfixExpressionList(String infixExpression) {
		// 定义一个 List，存放中缀表达式对应的内容。
		List<String> ls = new ArrayList<>();
		// 这是一个指针，用于遍历中缀表达式字符串。
		int index = 0;
		// 对多位数的拼接。
		String keepNumber;
		// 每遍历到一个字符，就放入到c
		char c;
		do {
			// 如果 c 是一个非数字，我们需要加入到 ls
			if ((c = infixExpression.charAt(index)) < 48 || (c = infixExpression.charAt(index)) > 57) {
				ls.add("" + c);
				index++;
			} else {
				// 如果是一个数，需要考虑多位数问题
				// 先将 keepNumber 转成"" '0'-> [48] '9' -> [57]
				keepNumber = "";
				while (index < infixExpression.length() && (c = infixExpression.charAt(index)) >= 48 && (c = infixExpression
						.charAt(index)) <= 57) {
					keepNumber += c;
					index++;
				}
				ls.add(keepNumber);
			}
		} while (index < infixExpression.length());
		return ls;
	}
	
	/**
	 * 分隔表达式，以List返回。
	 * @param suffixExpression 需要分割的表达式
	 * @return List 集合
	 */
	public static List<String> getListString(String suffixExpression) {
		// 将 suffixExpression 表达式分割
		String[] split = suffixExpression.split(" ");
		return new ArrayList<>(Arrays.asList(split));
	}
	
	/**
	 * 例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
	 * 1. 从左至右扫描，将3和4压入堆栈；
	 * 2. 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
	 * 3. 将5入栈；
	 * 4. 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
	 * 5. 将6入栈；
	 * 6. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
	 */
	public static int calculate(List<String> ls) {
		// 创建栈，只需要一个栈即可。
		Stack<String> stack = new Stack<>();
		
		// 遍历 ls
		for (String item : ls) {
			// 使用正则表达式来取出数，匹配的是多位数。
			if (item.matches("\\d+")) {
				// 入栈
				stack.push(item);
			} else {
				// pop 出两个数，并运算。再入栈。
				int num2 = Integer.parseInt(stack.pop());
				int num1 = Integer.parseInt(stack.pop());
				int res;
				switch (item) {
					case "+":
						res = num1 + num2;
						break;
					case "-":
						res = num1 - num2;
						break;
					case "*":
						res = num1 * num2;
						break;
					case "/":
						res = num1 / num2;
						break;
					default:
						throw new RuntimeException("输入有运算符有错误");
				}
				stack.push("" + res);
			}
		}
		return Integer.parseInt(stack.pop());
	}
	
	/**
	 * 一个静态内部类
	 * 返回一个运算符对应的优先级
	 */
	static class Operation {
		private static int ADD = 1;
		private static int SUB = 1;
		private static int MUL = 2;
		private static int DIV = 2;
		
		// 返回对应优先级数字的方法。
		public static int getPriority(String operation) {
			int result;
			switch (operation) {
				case "+":
					result = ADD;
					break;
				case "-":
					result = SUB;
					break;
				case "*":
					result = MUL;
					break;
				case "/":
					result = DIV;
					break;
				default:
					throw new RuntimeException("不存在该运算符");
			}
			return result;
		}
	}
}
